Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» ЗВІТ до лабораторної роботи № 3 з дисципліни «Програмування складних алгоритмів» Тема «Методи сортування» Варіант № 24 Дата «12» квітня 2022  Лабораторна робота № 3: Мета роботи: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Завдання до роботи Методичні вказівки Лабораторна робота спирається на знаннях отриманих при вивченні наступних питань лекції: – Поняття сортування. – Різних методів сортування. Завдання до лабораторної роботи: Розробити програму з алгоритмом згідно варіанту з використанням методів сортування. Оцінити час виконання та складність алгоритму. 1. Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням). 2. Самостійно обрати додатковий метод та провести сортування того ж масиву. 3. Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел Завдання / / 1.2. Теоретичні відомості Алгоритм сортування— процес, що впорядковує множину однотипних елементів за певною ознакою (ключем сортування). Сортування є типовою проблемою обробки даних, що забезпечує розміщення елементів невпорядкованого набору значень в порядку монотонного зростання або спадання значення ключа. Основні методи сортування масивів: Бульбашкове сортування — у вхідній послідовності порівнюються два сусідні елементи і, якщо вони не відповідають критерію сортування, ці елементи міняються місцями. Алгоритм працює доти, доки весь масив даних не буде впорядковано. Часова складність — O(n2). Сортування вставками — елементи вхідної послідовності проглядаються по одному, і кожен новий елемент, що надійшов, розміщується в придатне місце серед раніше упорядкованих елементів. Застосовується для майже цілком відсортованих даних та даних невеликого розміру. Часова складність — O(n2). Сортування вибором — поєднання бульбашкового сортування та сортування вставками. Як і у бульбашкового сортування, цей алгоритм проходить масивом раз за разом, переміщаючи одне значення на правильну позицію. Однак, на відміну від бульбашкового сортування, вибирає найменше невідсортоване значення замість найбільшого. Як і при сортуванні вставками, упорядкована частина масиву розташована на початку, тоді як у бульбашкового сортування — наприкінці. Часова складність — O(n2). Швидке сортування — алгоритм, який не потребує додаткової пам’яті, оскільки використовує прості цикли й операції, працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. З масиву обирається опорний елемент, і весь масив розбивається на дві частини: в першій — елементи, не більші даного, в другій — не менші. Впорядкування кожної з частин відбувається рекурсивно. Час роботи алгоритму сортування залежить від того, який елемент обрано як опорний. У найгіршому випадку час роботи алгоритму — O(n2), але математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах ближче до найкращого — O(n log n). 1.3. Результати роботи Завдання 1. Написано програмний код, який реалізує задачу відсортувати масив відповідно до наданого зразку. Сортування здійснюється за допомогою обмінного методу quickSort. Для порівняння швидкості роботи алгоритму додатково розроблено метод сортування bubbleSort.. У найгіршому випадку часова складність першого алгоритму — O(n2), але математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах ближче до найкращого — O(n log n). Часова складність другого алгоритму — O(n2). Нижче в таблиці представлено залежність часу виконання від розмірів масиву та відповідно кількості ітерацій. Спосіб сортування Розмір N*M Час виконання   Бульбашкове сортування 10*10 0,011 ms   1000*1000 131,592 ms   Швидке сортування 10*10 0,015 ms ...